package problem870;

import java.util.Arrays;

//870.优势洗牌
//https://leetcode.cn/problems/advantage-shuffle/

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Integer[] index1 = new Integer[n];
        Integer[] index2 = new Integer[n];
        for(int i = 0; i<n; i++) {
            index1[i] = index2[i] = i;
        }
        Arrays.sort(index1, (a,b)->nums1[a]-nums1[b]);
        Arrays.sort(index2, (a,b)->nums2[a]-nums2[b]);
        System.out.println(Arrays.toString(index1));
        System.out.println(Arrays.toString(index2));
        int[] arr = new int[n];
        int left = 0, right = n-1;
        int cur = 0;
        while(cur < n) {
            if(nums1[index1[cur]] > nums2[index2[left]]) {
                arr[index2[left++]] = nums1[index1[cur]];
            }else {
                arr[index2[right--]] = nums1[index1[cur]];
            }
            cur++;
        }
        return arr;
    }
}

//class Solution {
//    public static int[] advantageCount(int[] nums1, int[] nums2) {
//        int n = nums1.length;
//        Integer[] index1 = new Integer[n];
//        Integer[] index2 = new Integer[n];
//        for(int i = 0; i<n; i++) {
//            index1[i] = index2[i] = i;
//        }
//        Arrays.sort(index1, (a,b)->nums1[a]-nums1[b]);
//        Arrays.sort(index2, (a,b)->nums2[a]-nums2[b]);
//        System.out.println(Arrays.toString(index1));
//        System.out.println(Arrays.toString(index2));
//        int[] arr = new int[n];
//        int left = 0, right = n-1;
//        int i = 0, j = 0;
//        while(left < right) {
//            if(nums1[index1[i]] <= nums2[index2[j]]) {
//                arr[index2[right]] = nums1[i];
//                i++;
//                right--;
//            }else {
//                arr[index2[left]] = nums1[i];
//                i++;
//                j++;
//                left++;
//            }
//        }
//        return arr;
//    }
//
//    public static void main(String[] args) {
//        int[] nums1 = {12,24,8,32};
//        int[] nums2 = {13,25,32,11};
//        advantageCount(nums1, nums2);
//    }
//}